1. Field
This application relates to network elements and, more particularly, to a method for performing IP longest prefix match using prefix length sorting.
2. Description of the Related Art
Data communication networks may include various switches, nodes, routers, and other devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements”. Data is communicated through the data communication network by passing protocol data units, such as frames, packets, cells, or segments, between the network elements by utilizing one or more communication links. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
Network elements are designed to handle packets of data efficiently, to minimize the amount of delay associated with transmission of the data on the network. Conventionally, this is implemented by using hardware in a data plane of the network element to forward packets of data, while using software in a control plane of the network element to configure the network element to cooperate with other network elements on the network. For example, a network element may include a routing process, which runs in the control plane, that enables the network element to have a synchronized view of the network topology so that the network element is able to forward packets of data across the network toward its intended destination. Multiple processes may be running in the control plane to enable the network element to interact with other network elements on the network and forward data packets on the network.
The applications running in the control plane make decisions about how particular types of traffic should be handled by the network element to allow packets of data to be properly forwarded on the network. As these decisions are made, the control plane programs the hardware in the dataplane to enable the dataplane to be adjusted to properly handle traffic as it is received. The data plane includes ASICs, FPGAs, and other hardware elements designed to receive packets of data, perform lookup operations on specified fields of packet headers, and make forwarding decisions as to how the packet should be transmitted on the network. Lookup operations are typically implemented using tables and registers containing entries populated by the control plane.
Internet Protocol (IP) version 4 (IPv4) specifies a 32 bit addressing scheme to allow packets of data to be addressed on a network. A router will read the IP address, perform an IP lookup to determine a set of output ports, and forward the packet out the identified set of output ports toward its destination.
Although IPv4 addresses have 32 bits, not all of the bits may be relevant to a router when making a forwarding decision. For example, a given range of IP addresses may be commonly located within a particular sub-network area, such that all traffic addressed to an IP address within the range of IP addresses should be commonly forwarded by a router toward the subnet. In this situation, the less significant bits of the IP address are not relevant to the forwarding decision and, hence, the router may make a forwarding decision by looking only at the more significant bits of the IP address.
An IP address may therefore be viewed as having an address and a prefix length, e.g. address/16 would indicate that the prefix is 16 bits long such that only the 16 most significant bits of the address have forwarding significance. Since the entire range of IP addresses associated with the /16 prefix will be commonly forwarded out the same set of ports, the router may ignore the 16 least significant bits. The prefix thus specifies a range of IP addresses since all IP addresses with the same prefix will be forwarded according to the forwarding rule associated with the prefix. For example, a /16 bit prefix would represent a range of 64K IP addresses.
Since it is possible to have sub-ranges associated with different forwarding operations, a router will commonly implement a forwarding decision by looking for the longest prefix of the IP address which matches a routing entry in the forwarding table. This allows more specific routing information to take precedence over more general routing information. For example, a router may have a forwarding rule that packets matching a particular /16 prefix should be forwarded on a first set of ports, but that a sub-range of IP addresses matching a particular /24 prefix should be forwarded to a different destination on a second set of ports. Accordingly, when a router receives a packet, it performs a lookup operation to determine the longest prefix in its forwarding tables that matches the IP address contained in the packet. A lookup of this nature is referred to as Longest Prefix Match (LPM).
There are two common methods to implement hardware-based LPM lookup. The first method uses Ternary Content Addressable Memory (TCAM). A TCAM is a fully-associative memory that can store 0, 1 and don't care bits. In a single clock cycle, a TCAM chip finds the longest prefix that matches the address of the incoming packet by searching all stored prefixes in parallel. The issue with this method is that TCAM has high power consumption, poor scalability and higher cost compared to other memory technologies.
The second method is based on a multibit trie representation of a prefix table. In a multibit trie, one or more bits are scanned in a fixed or variable strides to direct the branching of the children. For example, a first lookup may use the first 4 bits of the IP address, the next two bits may then be used for a secondary lookup, etc., until the tree is traversed. The issue with this method is lookup latency. Since all memory accesses to traverse the tree are sequential, implementing an IP LPM using a multibit trie may require 6-10 memory accesses, which delays forwarding of the packet by the network element. Although latency and power consumption may be reduced by using very fast Static Random Access Memory, the latency gets worse when less expensive DDR2/3/4 SDRAM is used instead of SRAMs.